//
// Created by EmFi on 2023/5/14.
//

#ifndef DBMS_LEAFNODE_H
#define DBMS_LEAFNODE_H

#include <ostream>
#include "Node.h"

template<class K, class V>
class LeafNode : public Node<K> {
protected:
    // 值数组
    V *values;
    // 双向链表的前一个结点
    LeafNode<K, V> *prevNode;
    // 双向链表的后一个结点
    LeafNode<K, V> *nextNode;
public:
    explicit LeafNode(int order) : Node<K>(order) {
        this->type = NodeType::LEAF;
        this->prevNode = nullptr;
        this->nextNode = nullptr;
        this->values = new V[this->capacity];
    }

    ~LeafNode() {
        delete this->values;
    }

    // 将 key, val 插入到当前叶子节点
    bool insert(K key, V val) {
        // 如果当前结点已满，返回插入失败
        if (this->length >= this->capacity) {
            return false;
        }

        // 寻找插入的位置
        int index = 0;
        while (key > this->keys[index] && index < this->length) {
            index++;
        }

        // 将 index 及其后面的数据依次后移，空出当前位置
        for (int i = this->length; i >= index; i--) {
            this->keys[i] = this->keys[i - 1];
            this->values[i] = this->values[i - 1];
        }

        // 把数据存入当前位置
        this->keys[index] = key;
        this->values[index] = val;

        this->length++;

        return true;
    }

    // 从叶子节点删除 key
    bool remove(K key) {
        bool found = false;

        // 寻找删除的位置
        int index = 0;
        while (index < this->length) {
            if (key == this->keys[index]) {
                found = true;
                break;
            }
            index++;
        }

        // 如果没有找到，返回失败
        if (!found) {
            return false;
        }

        // 将 index 及其后面的节点依次前移
        for (int i = index; i < this->length - 1; i++) {
            this->keys[i] = this->keys[i + 1];
            this->values[i] = this->values[i + 1];
            this->keys[i + 1] = NULL;
            this->values[i + 1] = NULL;
        }

        this->length--;

        return true;
    }

    // 分裂叶子结点
    // 把本结点的后一半数据剪切到 newNode 中，返回分裂后两个节点的父节点的键
    K split(LeafNode<K, V> * newNode) {
        int moved = 0;
        for (int i = this->order; i < this->capacity; i++) {
            // 由于本节点的数据是有序的，因此新节点可以直接插入，无需调用 insert 方法
            newNode->keys[moved] = this->keys[i];
            newNode->values[moved] = this->values[i];
            // 清除已移动的节点数据
            this->keys[i] = NULL;
            this->values[i] = NULL;
            moved++;
        }

        // 重新设置两个节点的数据长度
        this->length -= moved;
        newNode->length = moved;

        // 处理叶子节点关系，保持叶子节点的双向链表特性
        newNode->setNextNode(this->getNextNode());
        if (this->getNextNode() != nullptr) {
            this->getNextNode()->setPrevNode(newNode);
        }
        this->setNextNode(newNode);
        newNode->setPrevNode(this);

        return newNode->keys[0];
    }

    // 合并叶子结点，将指定叶子结点的数据全部合并到本结点
    bool merge(LeafNode<K, V> *node) {
        // 如果两个节点的长度之和大于本节点容量，则不允许合并
        if (this->length + node->length > this->capacity) {
            return false;
        }

        for (int i = 0; i < node->length; i++) {
            // 由于另一个节点的数据顺序相当于本节点是未知的，因此调用 insert 方法进行插入
            this->insert(node->keys[i], node->values[i]);
        }

        // 由于不知道 node 和 this 的位置关系，叶子结点的双向链表指针调整需要在调用方实现

        return true;
    }

    // 在本叶子结点中查找 key 对应的 value，如果没找到返回 NULL
    V find(K key) {
        for (int i = 0; i < this->length; i++) {
            if (key == this->keys[i]) {
                return this->values[i];
            }
        }

        return NULL;
    }

    LeafNode<K, V> *getPrevNode() const {
        return this->prevNode;
    }

    void setPrevNode(LeafNode<K, V> *prev) {
        this->prevNode = prev;
    }

    LeafNode<K, V> *getNextNode() const {
        return this->nextNode;
    }

    void setNextNode(LeafNode<K, V> *next) {
        this->nextNode = next;
    }

    V getValue(int index) const {
        return this->values[index];
    }

    void setValue(int index, V val) {
        this->values[index] = val;
    }

    V *getValues() const {
        return this->values;
    }

    friend ostream &operator<<(ostream &os, const LeafNode &node) {
        os << "{" << &node << "} ";
        os << "[" << node.prevNode << "] ";
        for (int i = 0; i < node.length; i++) {
            os << node.keys[i] << "(" << node.values[i] << ")";
            if (i < node.length - 1) {
                os << " ";
            }
        }
        os << " [" << node.nextNode << "]";
        return os;
    }
};

#endif //DBMS_LEAFNODE_H
